package algorithm;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * Created by User on 2017/11/2.
 */
public class KMP算法和BM算法 {

    // 字符串s1是否包含字符串s2 包含返回位置
    public static void main(String[] args) throws IOException {
        /*StringBuilder sb = new StringBuilder();
        Random random = new Random();
        for (int i = 0; i < 1000000; i++) {
            sb.append(random.nextInt(10));
        }
        System.out.println(sb.toString());*/
        InputStream test = KMP算法和BM算法.class.getClassLoader().getResourceAsStream("test");
        byte[] bs = new byte[1024];

        int len = -1;
        StringBuilder result = new StringBuilder();

        while ((len = test.read(bs)) > -1) {
            result.append(new String(bs));
        }


        System.out.println(result.toString());
        String s1 = result.toString();


        String s2 = "451351";
        long l = System.currentTimeMillis();
        int match = new KMP(s1, s2).match();
        System.out.println(match);
        System.out.println(s1.substring(match, match + s2.length()));
        System.out.println(System.currentTimeMillis() - l);
        /*for (int index : match) {
            String substring = s1.substring(index, index + s2.length());
            System.out.println(substring);
            if (!substring.equals(s2)) System.out.println("error!!!");
        }*/
    }

    static class BM {
        char[] chars1;
        char[] chars2;

        public BM(String s1, String s2) {
            chars1 = s1.toCharArray();
            chars2 = s2.toCharArray();
        }

        List<Integer> matchedIndexList = new ArrayList<Integer>();

        int currentMatchIndex;
        int maxMarchIndex;

        public int match() {
            init();
            do {
                for (int i = currentMatchIndex, j = 0; i < chars1.length; i++) {
                    char c1 = chars1[i];
                    char c2 = chars2[j];
                    if (c1 != c2) break;
                    if (++j == chars2.length) { //匹配上了
                        return currentMatchIndex;
                    }
                }
            } while (++currentMatchIndex <= maxMarchIndex);

            return -1;
        }

        private void init() {
            currentMatchIndex = 0;
            maxMarchIndex = chars1.length - chars2.length;
        }


    }


    static class KMP {
        String s1;
        String s2;

        public KMP(String s1, String s2) {
            this.s1 = s1;
            this.s2 = s2;
        }

        List<Integer> matchedIndexList = new ArrayList<Integer>();

        int currentMatchIndex;
        int maxMarchIndex;
        int[] partMatchTable;

        public int match() {
            init();
            do {
                int matchingIndex = toMatch(currentMatchIndex);
                if (matchingIndex == s2.length()) return currentMatchIndex;
                currentMatchIndex += matchingIndex - partMatchTable[matchingIndex - 1];
            } while (currentMatchIndex <= maxMarchIndex);

            return -1;
        }

        private int toMatch(int sourceOffset) {
            for (int matchingIndex = 0; matchingIndex < s2.length(); matchingIndex++) {
                char c1 = s1.charAt(sourceOffset + matchingIndex);
                char c2 = s2.charAt(matchingIndex);
                if (c1 != c2) return ++matchingIndex;
            }
            return s2.length();
        }

        private void init() {
            currentMatchIndex = 0;
            maxMarchIndex = s1.length() - s2.length();
            partMatchTable = new int[s2.length()];
            // 部分匹配表
            for (int tIndex = 0; tIndex < s2.length() - 1; tIndex++) {
                partMatchTable[tIndex] = matchPreSuf(s2.substring(0, tIndex + 1));
            }
        }

        private int matchPreSuf(String str) {
            int len = str.length();
            for (int l = len - 1; l > 0; l--) {
                String pre = str.substring(0, l);
                String suf = str.substring(len - l, len);
                if (!pre.equals(suf)) continue;
                return l;
            }

            return 0;
        }

    }


    static class KMPSimple {
        String s1;
        String s2;

        public KMPSimple(String s1, String s2) {
            this.s1 = s1;
            this.s2 = s2;
        }

        public int match() {
            int sourceLen = s1.length();
            int targetLen = s2.length();
            int maxMarchIndex = sourceLen - targetLen;
            int currIndex = 0;
            do {
                int j = 0;
                for (int i = currIndex; i < sourceLen; i++) {
                    char c1 = s1.charAt(i);
                    char c2 = s2.charAt(j);
                    if (c1 != c2) break;
                    if (++j == targetLen) return currIndex;
                }
                currIndex += getMoveInterval(s2.substring(0, j));
            } while (currIndex <= maxMarchIndex);

            return -1;
        }

        int[] cacheForInterval;

        public int getMoveInterval(String str) {
            checkCache();

            int strLen = str.length();

            if (strLen == 0) return 1;

            int cache;
            if ((cache = cacheForInterval[strLen - 1]) != -1) return cache;

            int interval = strLen;

            for (int i = strLen - 1; i > 0; i--) {
                if (str.substring(0, i).equals(str.substring(strLen - i, strLen))) {
                    interval -= i;
                }
            }

            return interval;
        }

        public void checkCache() {
            if (cacheForInterval == null) {
                cacheForInterval = new int[s2.length()];
                for (int i = 0; i < cacheForInterval.length; cacheForInterval[i] = -1, i++);
            }
        }

    }

}
